1. Field of the Invention
This invention relates generally to digital image processing and more particularly to systems for rendering high quality images through halftoning.
2. Background of the Invention
Color digital images are multidimensional. An image is sampled in two-dimensions and the smallest unit in the two-dimensional plane that can be individually recognized, stored or processed is called a picture element (pixel or pel). Each pixel will have a certain size (height and width) in the two-dimensional plane but will also be characterized in a third dimension that represents its tone intensity. This will be a quantized value or values. For example, a color image may be represented by three quantized values per pixel, one value each for red, green and blue. The image texture will be affected, in part, by the number of quantization levels. For example, 256 quantization levels (ranging from 0 to 255) can be represented with 8 bits/color. Another factor that affects image texture is the sampling resolution and in order to achieve good quality at low quantization levels high resolution is required.
Although a color image may be scanned and stored, or computer generated, with a relatively large number of quantization levels, image rendering devices such as color printers are capable of producing far less quantization levels, typically two-print a dot at a pixel location or not print a dot at a pixel location.
In order to render the original or source, high quantization (e.g. 8 bits/color/pixel precision) image with an output, low quantization (e.g. 1 bit/color/pixel precision) device, the high quantization image must be converted into a bilevel image pattern that the human visual system will tend to integrate over areas into the higher quantization level source image. This is possible because of the limited visual ability to discriminate between small differences in tonal ranges at a normal viewing distance. This rendering process is referred to as halftoning. Generally speaking, the source image is divided into small sub-areas each with a number of pixels. The pixels in the sub-area are printed or not printed so that when the sub-area is viewed at a distance it simulates a gray or color sensation.
A widely employed approach to performing digital halftoning is referred to as ordered-dither halftoning. In this process a halftone cell is first established. This halftone cell is a matrix or array of threshold values. A great deal of research goes into establishing the threshold pattern of the cell so that it ensures a smooth transition of tone across the tonal range. The halftone cell is conceptually overlaid on a sub-area of the source image and each threshold value in the array is compared with an associated pixel value in the source image. The halftone cell is moved over each sub-area until it tiles the entire source image. The culmination of these threshold value/pixel value comparisons is a bilevel image that simulates the original source image.
A variety of dither-array pattern types have been proposed and used, each of which has its own advantages and disadvantages. The type commonly referred to as xe2x80x9cclustered-dotxe2x80x9d dithering employs a dither matrix in which higher values tend to be clustered near other higher values, and lower values tend to be clustered near other lower values. A uniform gray level is rendered in the binary image as clusters of printed pixels, the cluster size depending on the underlying gray value. The resultant image is visually similar to those produced by the traditional half-tone photoengraving screen. An advantage of clustered-dot dithering is that it compensates for the inability of certain display devices to display isolated pixels.
For example, in laser printers, typically, the laser beam scans from left to right and/or right to left in successive rows as it prints on the page. In this way, it renders an image in a raster-scan format as discrete picture-element (pixel) values. This representation, as well as processing employed to command the printer to render the image, are based on the assumption of a regular pixel spacing: the row-to-row spacing is assumed to be uniform. In reality, however, even slight misregistrations can cause artifacts in the printed image.
One of the undesirable visual artifacts of this misregistration or lack of uniformity in pixel spacing is a type of banding that is sometimes seen in regions where the display device is attempting to render a uniform gray or other color level, especially in the light tones. Instead of the uniform color, the non-uniform scan-line spacing ends up causing bands of lighter and darker regions. This typically results from interaction of the non-uniform line spacing with the half-toning process that the printer uses to render shades of gray.
At any given pixel, devices such as laser printers are typically capable only of on-and off operation: they either form a dot in the pixel or not. In order to render gray-scale values, printers rely instead on duty cycle. In regions that are intended to be darker, more pixels receive dots. In lighter regions, fewer do. One way of achieving this result is to have groups of dots form clusters, which are larger or smaller in accordance with the intended gray level to be rendered. Non-uniform spacing can make clusters formed by different row sequences differ in size and thereby cause unintended variations in displayed color. These variations tend to form undesirable visible bands.
One can attempt to avoid this effect by employing different half-toning techniques, such as distributed-dot dithering, in which the xe2x80x9cturned-onxe2x80x9d pixels are not clustered together. Because clusters generally do not form, non-uniform scan-line spacing does not change cluster size, so the non-uniform line spacing is less evident. However this method is not well suited to laser printers that are limited in their ability to print isolated pixels.
Therefore, it is an object of the present invention to overcome the aforementioned problems.
A further object of the invention is to provide a halftoning system that is ideally suited for use in display devices with limited capability in displaying isolated pixels.
Another object of the invention is to minimize the banding effect even when using clustered-dot dithering.
Typically in laser printers a dither matrix is employed for cluster-dot dithering. The dither matrix is tiled over the entire input image. It is moved over one sub-area and each threshold value of the dither matrix is compared to the tone intensity or value of the corresponding pixel in the image sub-area. The result is clusters of dots in the sub-area of the resultant image, the number and/or size of the dot clusters will depend on the tone intensity of the sub-area. In prior methods, the same dither matrix is then moved over the next sub-area and again the same threshold values in the same relative locations in the dither matrix are compared with the corresponding pixel values of this next-sub-area. As this process is repeated throughout the image, clusters formed by different row sequences may differ in size even in areas of the image that have a uniform tone intensity. In light tone areas especially, these clusters of one size in one row and clusters of a second size in a different row show up as bands. As mentioned previously, this banding effect is generally caused by the interaction of non-uniform line-spacing with the dither matrix.
We have found that we can lessen the effect of this interaction if we change the dither matrix as it moves over the image. We do this by modulating the dither matrix (halftone cell) as a function of the spatial position of the sub-area in the image. Halftone cells can be formed in a variety of patterns (e.g. vertical, horizontal, etc.) but generally their threshold values grow from a minimum value to a maximum value. Our process is to modulate the halftone cell according to a function: f (s, h) where s is the spatial position of the sub-area of the image and h is the halftone cell. We modulate the cell by altering the relative positions of the threshold values in the cell as we move the cell over the image. This effectively breaks up the bands of clusters of one size or another and provides a visually uniform image even in lighter tones.
Other objects and attainments together with a fuller understanding of the invention will become apparent and appreciated by referring to the following description and claims taken in conjunction with the accompanying drawings.